package offer;

import java.util.HashMap;

public class Solution7 {
    private HashMap<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preorder, int indexOfRoot, int start, int end) {
        if (start > end) {
            return null;
        }
        int valOfRoot = preorder[indexOfRoot];
        TreeNode root = new TreeNode(valOfRoot);
        int i = indexMap.get(valOfRoot);  //i：中序遍历中根结点的下标

        root.left = buildTree(preorder, indexOfRoot + 1, start, i - 1);
        root.right = buildTree(preorder, indexOfRoot + i - start + 1, i + 1, end);
        return root;
    }
}
